#define LINKLIST_STACK_LINKLIST_STACK_H
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

enum status{OK=1,ERROR=-2,TRUE=1,FALSE=0,EMPTY=-1,OVERFLOW=-3};
//typedef enum status status;

typedef int status;

typedef struct sNode
{
    int data;
    struct sNode *below;
}sNode;

typedef struct 
{
    sNode *base;
    sNode *top;
    int StackSize;
}linkstack;

status Initstack(linkstack *S);//构造空栈
status Destorystack(linkstack *S);//销毁栈S；
status clearstack(linkstack *S);//把栈置为空栈
status stackempty(linkstack S);//若栈为空栈返回true，否则返回false
int stacklength(linkstack S);//判断栈的长度
int* gettop(linkstack S);//返回栈顶元素；
status push(linkstack* S,int e);//插入e为栈顶元素；
int* pop(linkstack *S);//删除栈顶元素，并返回；
status stackTraverse(linkstack S,status (*visit)(int));//遍历栈

//构造空栈
status Initstack(linkstack *S)
{
   S->base=NULL;//初始化栈
   S->top=S->base;
   S->StackSize=0;
   return OK;
}

//销毁栈
status Destorystack(linkstack *S)
{
     if (S==NULL)
    {
        return -2;
    }
    sNode* Ptmp=S->top->below;//保存下一个栈结点的地址
    while (S->top!=NUll)
    {
        free (S->top);//释放当前节点空间
        S->top=Ptmp;//栈顶指针指向下一个节点位置
        Ptmp=S->top->below;//更新保存节点位置
    }
    free(S);//释放栈空间
    S=NULL;
    return OK;
}

//把栈置为空栈
status clearstack(linkstack *S)
{
    if (S==NUll||S->base==NUll)
    {
        return ERROR;
    }
    sNode* Ptmp=S->top->below;//保存下一个栈结点的地址
    while (S->top!=NUll)
    {
        free (S->top);//释放当前节点空间
        S->top=Ptmp;//栈顶指针指向下一个节点位置
        if (S->top!=NULL)
        {
            Ptmp=S->top->below;//更新保存节点位置
        }
    }
    S->top=S->base;
    S->StackSize=NULL;
    return OK;
}

//判断栈是否为空
status stackempty(linkstack S)
{
    if (S.base==NULL)
    {
        return ERROR;
    }
    if (S.base==S.top)
    {
        return TRUE;
    }
    else    return FALSE;
}

//判断栈的长度
int stacklength(linkstack S)
{
    if (S.base==NULL)
    {
        return ERROR;
    }
    return (int)(S.StackSize)/(int)(sizeof(sNode));//总空间大小/每个元素的大小=元素个数
}

//返回到栈顶元素
int* gettop(linkstack S)
{
    int *re;//用于保存栈顶元素的值
    if (S.top==S.base)
    {
        return NULL;
    }
    re=(S.top->data);
    return re;
}

//插入e为栈顶元素
status push(linkstack* S,int e)
{
    sNode *newE=(sNode*)malloc(sizeof(sNode));//为新节点创建空间
    if (!newE)
    {
        return ERROR;//如果空间已满，分配失败
    }
    newE->below=NULL;
    newE->data=(int*)malloc(sizeof(int));
    *newE->data=e;
    if (S->top==NULL)
    {
        S->base=newE;
        S->top=newE;
    }
    else{
        newE->below=S->top;
        S->top=newE;
    }
    //更新栈数据
    S->StackSize+=(sizeof(sNode));
    return OK;
}

//删除并返回栈顶元素
int* pop(linkstack *S)
{
    int *re;//用于返回栈顶元素
    if (S->top==S->base)
    {
        return ERROR;
    }
    sNode *ptmp=S->top->below;
    re=S->top->data;//为返回的元素赋值
    free(S->top);//释放栈顶元素空间
    S->top=ptmp;
    S->StackSize-=(sizeof(sNode))
    return re;
}

//遍历栈
void stackfortraverse(sNode *p,status(*visit)(int))
{
    if (p!=NULL)
    {
        stackfortraverse(p->below,visit);
        visit(*p->data);
    }
    
}

status stackTraverse(linkstack S,status (*visit)(int))
{
    if (S.base==NULL)
    {
        return NULL;
    }
    stackfortraverse(S.top,visit);
    return OK;
}

int main()
{
    linkstack S;
    if (Initstack(&S))
    {
        printf("初始化成功\n");
    }
    else
    {
        printf("初始化失败\n");
    }
    //入栈
    int n;
	printf("请输入栈的元素个数:");
	scanf("%d",&n);
	for (int i = 0; i < n;)
	{
		int e;
		printf("请输入第%d个入栈的元素:",++i);
		scanf("%d", &e);
		Push(&S, e);
	}
    stackTraverse(S,visit);//遍历栈；
    printf("栈的长度为：%d\n",stacklength(S));//判断栈的长度
    //把栈置空
    if (clearstack(&S))
    {
        printf("置空成功\n");
    }
    else
    {
        printf("置空失败")
    }
    //判断栈是否为空
    if (stackempty(S))
    {
        printf("栈为空\n");
    }
    else
    {
        printf("栈不为空\n");
    }
    //销毁栈
    if (Destorystack(&S))
    {
        printf("成功销毁栈\n");
    }
    else
    {
        printf("销毁失败\n");
    }
    return 0;
}